package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202410;

import java.util.HashMap;
import java.util.Map;

public class leetcode20241011 {

    /**
     * 优质数对的总数：枚举因子
     * @param nums1
     * @param nums2
     * @param k
     * @return
     */
    public long numberOfPairs(int[] nums1,int[] nums2,int k){
        Map<Integer,Integer> cnt=new HashMap<>();
        for(int x : nums1){
            if(x%k!=0) continue;
            x/=k;
            for(int d=1;d*d<=x;d++){
                if(x%d>0) continue;
                 cnt.merge(d,1,Integer::sum);
                 if(d*d<x){
                     cnt.merge(x/d,1,Integer::sum);
                 }
            }
        }
        long ans=0;
        for(int x : nums2){
            ans+=cnt.getOrDefault(x,0);
        }
        return ans;
    }
}
